package com.cdream.basic.algorithm.leetcode.bfs;

import java.util.*;

public class Question815 {
    Map<Integer, Set<Integer>> busLineMap = new HashMap<>();
    //用过该公交车
    Map<Integer, Integer> usedLine = new HashMap<>();

    public int numBusesToDestination(int[][] routes, int source, int target) {
        // 线路Queue
        LinkedList<Integer> lineQueue = new LinkedList<>();

        if (source == target) {
            return 0;
        }
        // 某一个车站经过的所有线路
        for (int i = 0; i < routes.length; i++) {
            for (int j = 0; j < routes[i].length; j++) {
                Set<Integer> busList = busLineMap.getOrDefault(routes[i][j], new HashSet<>());
                busList.add(i);
                busLineMap.put(routes[i][j], busList);
            }
        }

        Set<Integer> lines = busLineMap.get(source);
        for (Integer line : lines) {
            lineQueue.offer(line);
            usedLine.put(line,1);
        }

        while (!lineQueue.isEmpty()) {
            Integer line = lineQueue.poll();
            int[] buses = routes[line];
            for (int bus : buses) {
                if (bus == target) {
                    return usedLine.getOrDefault(line, 0);
                }
                Set<Integer> nextLines = busLineMap.get(bus);
                int step = usedLine.getOrDefault(line,0);
                for (Integer nextLine : nextLines) {
                    if (usedLine.containsKey(nextLine)){
                        continue;
                    }
                    lineQueue.offer(nextLine);
                    usedLine.put(nextLine,step+1);

                }
            }

        }
        return -1;
    }

    public static void main(String[] args) {
        new Question815().numBusesToDestination(new int[][]{{1,2,7},{3,6,7}},1,6);
    }
}
